<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>合并两个有序链表 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        
        .card-shadow {
            box-shadow: 0 20px 40px rgba(0, 0, 0, 0.1);
            transition: all 0.3s ease;
        }
        
        .card-shadow:hover {
            transform: translateY(-5px);
            box-shadow: 0 25px 50px rgba(0, 0, 0, 0.15);
        }
        
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
            position: relative;
        }
        
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            display: flex;
            align-items: center;
            gap: 8px;
        }
        
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
            color: #d4d4d4;
            font-family: 'Consolas', 'Monaco', monospace;
            font-size: 14px;
            line-height: 1.6;
        }
        
        .keyword { color: #569cd6; }
        .type { color: #4ec9b0; }
        .comment { color: #6a9955; }
        .string { color: #ce9178; }
        .number { color: #b5cea8; }
        .function { color: #dcdcaa; }
        
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 3rem;
            padding-right: 0.5rem;
            margin-top: 0.5rem;
            font-weight: 700;
            color: #667eea;
        }
        
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        
        .complexity-badge {
            background: linear-gradient(135deg, #f093fb 0%, #f5576c 100%);
            color: white;
            padding: 4px 12px;
            border-radius: 20px;
            font-size: 0.875rem;
            font-weight: 500;
            display: inline-block;
            margin: 0 4px;
        }
        
        .step-number {
            width: 40px;
            height: 40px;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            color: white;
            border-radius: 50%;
            display: flex;
            align-items: center;
            justify-content: center;
            font-weight: 700;
            flex-shrink: 0;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20">
        <div class="container mx-auto px-6 text-center">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 animate-pulse">
                <i class="fas fa-link mr-4"></i>合并两个有序链表
            </h1>
            <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto">
                掌握链表操作的经典算法，优雅地将两个升序链表合并为一个新的升序链表
            </p>
            <div class="mt-8 flex justify-center gap-4 flex-wrap">
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full">
                    <i class="fas fa-code mr-2"></i>链表操作
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full">
                    <i class="fas fa-sort-amount-up mr-2"></i>归并算法
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full">
                    <i class="fas fa-brain mr-2"></i>面试高频
                </span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="container mx-auto px-6 py-12 max-w-6xl">
        <!-- Problem Description Card -->
        <div class="bg-white rounded-2xl card-shadow p-8 mb-8">
            <h2 class="text-3xl font-bold mb-6 text-gray-800">
                <i class="fas fa-question-circle text-purple-600 mr-3"></i>题目描述
            </h2>
            <p class="text-lg text-gray-700 leading-relaxed">
                <span class="drop-cap">将</span>两个升序链表合并为一个新的升序链表并返回。新链表由给定的两个链表的所有节点组成。
            </p>
            <div class="mt-6 bg-gray-50 rounded-xl p-6">
                <h3 class="font-semibold text-gray-800 mb-3">
                    <i class="fas fa-lightbulb text-yellow-500 mr-2"></i>示例
                </h3>
                <div class="font-mono text-gray-700">
                    <p>输入：1→2→4 和 1→3→4</p>
                    <p>输出：1→1→2→3→4→4</p>
                </div>
            </div>
        </div>

        <!-- Visual Representation -->
        <div class="bg-white rounded-2xl card-shadow p-8 mb-8">
            <h2 class="text-3xl font-bold mb-6 text-gray-800">
                <i class="fas fa-project-diagram text-purple-600 mr-3"></i>算法可视化
            </h2>
            <div class="mermaid">
                graph LR
                    subgraph "链表1"
                        A1[1] --> A2[2] --> A4[4]
                    end
                    subgraph "链表2"
                        B1[1] --> B3[3] --> B4[4]
                    end
                    subgraph "合并后"
                        C1[1] --> C2[1] --> C3[2] --> C4[3] --> C5[4] --> C6[4]
                    end
                    A1 -.-> C1
                    B1 -.-> C2
                    A2 -.-> C3
                    B3 -.-> C4
                    A4 -.-> C5
                    B4 -.-> C6
                    style A1 fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                    style A2 fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                    style A4 fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                    style B1 fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                    style B3 fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                    style B4 fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                    style C1 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
                    style C2 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
                    style C3 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
                    style C4 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
                    style C5 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
                    style C6 fill:#4CAF50,stroke:#333,stroke-width:2px,color:#fff
            </div>
        </div>

        <!-- Solution Approaches -->
        <div class="grid md:grid-cols-2 gap-8 mb-8">
            <!-- Iterative Approach -->
            <div class="bg-white rounded-2xl card-shadow p-8">
                <h3 class="text-2xl font-bold mb-4 text-gray-800">
                    <i class="fas fa-sync-alt text-blue-600 mr-3"></i>迭代法
                </h3>
                <p class="text-gray-700 mb-4">
                    使用哑节点（dummy node）简化操作，比较两个链表的节点值，依次合并。
                </p>
                <div class="space-y-3">
                    <div class="flex items-start gap-3">
                        <div class="step-number">1</div>
                        <p class="text-gray-700 pt-2">创建哑节点作为起点</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">2</div>
                        <p class="text-gray-700 pt-2">比较两链表当前节点值</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">3</div>
                        <p class="text-gray-700 pt-2">选择较小值加入结果链表</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">4</div>
                        <p class="text-gray-700 pt-2">处理剩余节点</p>
                    </div>
                </div>
                <div class="mt-6 flex gap-2">
                    <span class="complexity-badge">时间 O(n+m)</span>
                    <span class="complexity-badge">空间 O(1)</span>
                </div>
            </div>

            <!-- Recursive Approach -->
            <div class="bg-white rounded-2xl card-shadow p-8">
                <h3 class="text-2xl font-bold mb-4 text-gray-800">
                    <i class="fas fa-redo text-green-600 mr-3"></i>递归法
                </h3>
                <p class="text-gray-700 mb-4">
                    递归选择较小值的节点作为新链表的头，递归处理剩余部分。
                </p>
                <div class="space-y-3">
                    <div class="flex items-start gap-3">
                        <div class="step-number">1</div>
                        <p class="text-gray-700 pt-2">处理基础情况（空链表）</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">2</div>
                        <p class="text-gray-700 pt-2">比较两链表头节点</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">3</div>
                        <p class="text-gray-700 pt-2">选择较小值作为头</p>
                    </div>
                    <div class="flex items-start gap-3">
                        <div class="step-number">4</div>
                        <p class="text-gray-700 pt-2">递归合并剩余部分</p>
                    </div>
                </div>
                <div class="mt-6 flex gap-2">
                    <span class="complexity-badge">时间 O(n+m)</span>
                    <span class="complexity-badge">空间 O(n+m)</span>
                </div>
            </div>
        </div>

        <!-- Code Implementation -->
        <div class="bg-white rounded-2xl card-shadow p-8 mb-8">
            <h2 class="text-3xl font-bold mb-6 text-gray-800">
                <i class="fas fa-code text-purple-600 mr-3"></i>代码实现
            </h2>
            
            <div class="code-block">
                <div class="code-header">
                    <div class="code-dot bg-red-500"></div>
                    <div class="code-dot bg-yellow-500"></div>
                    <div class="code-dot bg-green-500"></div>
                    <span class="text-gray-400 ml-4">Java</span>
                </div>
                <pre><code><span class="comment">/**
 * 链表节点定义
 */</span>
<span class="keyword">public class</span> <span class="type">ListNode</span> {
    <span class="keyword">int</span> val;
    <span class="type">ListNode</span> next;
    <span class="function">ListNode</span>() {}
    <span class="function">ListNode</span>(<span class="keyword">int</span> val) { <span class="keyword">this</span>.val = val; }
    <span class="function">ListNode</span>(<span class="keyword">int</span> val, <span class="type">ListNode</span> next) { <span class="keyword">this</span>.val = val; <span class="keyword">this</span>.next = next; }
}

<span class="keyword">public</span> <span class="type">ListNode</span> <span class="function">mergeTwoLists</span>(<span class="type">ListNode</span> l1, <span class="type">ListNode</span> l2) {
    <span class="comment">// 创建哑节点作为合并链表的起点，简化边界情况处理</span>
    <span class="type">ListNode</span> dummy = <span class="keyword">new</span> <span class="type">ListNode</span>(<span class="number">0</span>);
    <span class="comment">